# leetcode 454, 四数相加II


#遍历前两个数组，然后遍历后两个
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        abmap  = {} # {nums1[a]+nums2[b]: [(a, b)]}
        n = len(nums1)
        for i in range(n): # 遍历nums1
            for j in range(n): # 遍历nums2
                if nums1[i] + nums2[j] in abmap:
                    abmap[nums1[i] + nums2[j]].append((i, j))
                else:
                    abmap[nums1[i] + nums2[j]] = [(i, j)]
        cdmap = {}
        count = 0
        for k in range(n):
            for l in range(n):
                tmp = nums3[k] + nums4[l]
                match = 0 - tmp
                if match in abmap:
                    count += len(abmap[match])
        return count



# 降低内存消耗，加速
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        abmap  = {} # {nums1[a]+nums2[b]: [(a, b)]}
        n = len(nums1)
        for i in range(n): # 遍历nums1
            for j in range(n): # 遍历nums2
                if nums1[i] + nums2[j] in abmap:
                    abmap[nums1[i] + nums2[j]] += 1
                else:
                    abmap[nums1[i] + nums2[j]] = 1
        cdmap = {}
        count = 0
        for k in range(n):
            for l in range(n):
                tmp = nums3[k] + nums4[l]
                match = 0 - tmp
                if match in abmap:
                    count += abmap[match]
        return count
